package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Queue;
import com.tyrone.algorithm.priority.MinPriorityQueue;
import com.tyrone.algorithm.uf.UF_Tree_Weighted;

/**
 *      Kruskal算法计算最小生成树
 */
public class KruskalMST {
    private Queue mst;                                //保存最小生成树的所有边
    private UF_Tree_Weighted uf;                      //索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在 同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
    private MinPriorityQueue<Edge> pq;                      //存储图中所有的边，使用最小优先队列，对边按照权重进行排序

    public KruskalMST(EdgeWeightedGraph G){
        this.mst = new Queue<Edge>();
        this.uf = new UF_Tree_Weighted(G.V());
        this.pq = new MinPriorityQueue(G.E()+1);
        for (Edge edge : G.edges()) {
            pq.insert(edge);
        }
        while (!pq.isEmpty()&&mst.size()<G.V()-1){
            Edge edge = pq.delMin();
            int v = edge.either();
            int w  = edge.other(v);
            if (uf.connected(v,w)){
                continue;
            }
            uf.union(v,w);
            mst.enqueue(edge);
        }
    }

    /**
     * 获取最小生成树的所有边
     * @return
     */
    public Queue<Edge> edges(){
        return mst;
    }
}
